SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Erasure code</title>

</head>

Erasure code

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, an erasure code is a <a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">forward error correction</a> (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be recovered from a subset of the n symbols. The fraction r = k/n is called the <a href="Code_rate" title="Code rate">code rate</a>. The fraction k’/k, where k’ denotes the number of symbols required for recovery, is called reception efficiency. The recovery algorithm expects that it is known which of the n symbols are lost.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

Erasure coding was invented by <a href="Irving_Reed" class="mw-redirect" title="Irving Reed">Irving Reed</a> and <a href="Gustave_Solomon" title="Gustave Solomon">Gustave Solomon</a> in 1960.<a href="#cite_note-xinnor-1">[1]</a>

There are many different erasure coding schemes. The most popular erasure codes are

<a href="Reed-Solomon_coding" class="mw-redirect" title="Reed-Solomon coding">Reed-Solomon coding</a>,

<a href="Low-density_parity-check_code" title="Low-density parity-check code">Low-density parity-check code</a> (LDPC codes), and

<a href="Turbo_codes" class="mw-redirect" title="Turbo codes">Turbo codes</a>.<a href="#cite_note-xinnor-1">[1]</a>

As of 2023, modern data storage systems can be designed to tolerate the complete failure of a few disks without data loss, using one of 3 approaches:<a href="#cite_note-2">[2]</a><a href="#cite_note-bdr-3">[3]</a><a href="#cite_note-jor-4">[4]</a>

<ul><li>Replication</li>

<li>Erasure Coding</li></ul>

While technically RAID can be seen as a kind of erasure code,<a href="#cite_note-5">[5]</a>

"RAID" is generally applied to an array attached to a single host computer (which is a single point of failure), while "erasure coding" generally implies multiple hosts,<a href="#cite_note-bdr-3">[3]</a>

sometimes called a <a href="Redundant_Array_of_Inexpensive_Servers" title="Redundant Array of Inexpensive Servers">Redundant Array of Inexpensive Servers</a> (RAIS).

The erasure code allows operations to continue when any one of those hosts stops.<a href="#cite_note-jor-4">[4]</a><a href="#cite_note-6">[6]</a>

Compared to block-level RAID systems, object storage erasure coding has some significant differences that make it more resilient.<a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a><a href="#cite_note-10">[10]</a><a href="#cite_note-11">[11]</a>

<div class="mw-heading mw-heading2"><h2 id="Optimal_erasure_codes">Optimal erasure codes</h2></div>

Optimal erasure codes have the property that any k out of the n code word symbols are sufficient to recover the original message (i.e., they have optimal reception efficiency). Optimal erasure codes are <a href="Maximum_distance_separable_code" class="mw-redirect" title="Maximum distance separable code">maximum distance separable codes</a> (MDS codes).

<div class="mw-heading mw-heading3"><h3 id="Parity_check">Parity check</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Parity_bit" title="Parity bit">Parity bit</a></div>

Parity check is the special case where n = k + 1. From a set of k values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v_{i}\}_{1\leq i\leq k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v_{i}\}_{1\leq i\leq k}}</annotation>

</semantics>

</math><img src="./573d09cd0202dd79bfc3942292d22f1db8ec544d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.287ex; height:2.843ex;" alt="{\displaystyle \{v_{i}\}_{1\leq i\leq k}}" loading="lazy">, a checksum is computed and appended to the k source values:

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}</annotation>

</semantics>

</math><img src="./e55976b0f7ab47062c8b911edcd8cb8b96ed5f77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.927ex; height:7.343ex;" alt="{\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}" loading="lazy"></dd></dl>

The set of k + 1 values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}</annotation>

</semantics>

</math><img src="./0baae8ab63c08b79ccb9f0016654cbac2410e6c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.388ex; height:2.843ex;" alt="{\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}" loading="lazy"> is now consistent with regard to the checksum.

If one of these values, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{e}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{e}}</annotation>

</semantics>

</math><img src="./3271a14c35fc1b6cb549d4d462e8d3255185cc9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.126ex; height:2.009ex;" alt="{\displaystyle v_{e}}" loading="lazy">, is erased, it can be easily recovered by summing the remaining variables:

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}</annotation>

</semantics>

</math><img src="./ad307f6fa582b03f30b2862167c8c081dfb8d7ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:16.118ex; height:7.843ex;" alt="{\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}" loading="lazy"></dd></dl>

<a href="RAID_5" class="mw-redirect" title="RAID 5">RAID 5</a> is a widely used application of the parity check erasure code.<a href="#cite_note-xinnor-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Polynomial_oversampling">Polynomial oversampling</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Example:_Err-mail_(k_=_2)">Example: Err-mail (k = 2)</h4></div>

In the simple case where k = 2, redundancy symbols may be created by sampling different points along the line between the two original symbols. This is pictured with a simple example, called err-mail:

<a href="Alice_and_Bob" title="Alice and Bob">Alice</a> wants to send her telephone number (555629) to <a href="Alice_and_Bob" title="Alice and Bob">Bob</a> using err-mail. Err-mail works just like e-mail, except

<ol><li>About half of all the mail gets lost.</li>

<li>Messages longer than 5 characters are illegal.</li>

<li>It is very expensive (similar to air-mail).</li></ol>

Instead of asking Bob to acknowledge the messages she sends, Alice devises the following scheme.

<ol><li>She breaks her telephone number up into two parts a = 555, b = 629, and sends 2 messages – "A=555" and "B=629" – to Bob.</li>

<li>She constructs a linear function, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(i)=a+(b-a)(i-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(i)=a+(b-a)(i-1)}</annotation>

</semantics>

</math><img src="./787418947869c492a669e3234a995506be6de067.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.551ex; height:2.843ex;" alt="{\displaystyle f(i)=a+(b-a)(i-1)}" loading="lazy">, in this case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(i)=555+74(i-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(i)=555+74(i-1)}</annotation>

</semantics>

</math><img src="./4d59837a716631513cd3d9446656bbbf61af524e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.256ex; height:2.843ex;" alt="{\displaystyle f(i)=555+74(i-1)}" loading="lazy">, such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(1)=555}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(1)=555}</annotation>

</semantics>

</math><img src="./08b0a94af48f47edbb04714c0805744f34903cf9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.836ex; height:2.843ex;" alt="{\displaystyle f(1)=555}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(2)=629}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(2)=629}</annotation>

</semantics>

</math><img src="./f41b533ea5368aae812e068489dba01461e838d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.836ex; height:2.843ex;" alt="{\displaystyle f(2)=629}" loading="lazy">.</li></ol>

<ol><li>She computes the values f(3), f(4), and f(5), and then transmits three redundant messages: "C=703", "D=777" and "E=851".</li></ol>

Bob knows that the form of f(k) is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(i)=a+(b-a)(i-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(i)=a+(b-a)(i-1)}</annotation>

</semantics>

Now suppose Bob receives "D=777" and "E=851".

Bob can reconstruct Alice's phone number by computing the values of a and b from the values (f(4) and f(5)) he has received.

Bob can perform this procedure using any two err-mails, so the erasure code in this example has a rate of 40%.

Note that Alice cannot encode her telephone number in just one err-mail, because it contains six characters, and that the maximum length of one err-mail message is five characters. If she sent her phone number in pieces, asking Bob to acknowledge receipt of each piece, at least four messages would have to be sent anyway (two from Alice, and two acknowledgments from Bob). So the erasure code in this example, which requires five messages, is quite economical.

This example is a little bit contrived. For truly generic erasure codes that work over any data set, we would need something other than the f(i) given.

<div class="mw-heading mw-heading4"><h4 id="General_case">General case</h4></div>

The linear construction above can be generalized to <a href="Polynomial_interpolation" title="Polynomial interpolation">polynomial interpolation</a>. Additionally, points are now computed over a <a href="Finite_field" title="Finite field">finite field</a>.

First we choose a finite field F with order of at least n, but usually a power of 2. The sender numbers the data symbols from 0 to k − 1 and sends them. He then constructs a <a href="Lagrange_polynomial" title="Lagrange polynomial">(Lagrange) polynomial</a> p(x) of order k such that p(i) is equal to data symbol i. He then sends p(k), ..., p(n − 1). The receiver can now also use polynomial interpolation to recover the lost packets, provided he receives k symbols successfully. If the order of F is less than 2b, where b is the number of bits in a symbol, then multiple polynomials can be used.

The sender can construct symbols k to n − 1 'on the fly', i.e., distribute the workload evenly between transmission of the symbols. If the receiver wants to do his calculations 'on the fly', he can construct a new polynomial q, such that q(i) = p(i) if symbol i < k was received successfully and q(i) = 0 when symbol i < k was not received. Now let r(i) = p(i) − q(i). Firstly we know that r(i) = 0 if symbol i < k has been received successfully. Secondly, if symbol i ≥ k has been received successfully, then r(i) = p(i) − q(i) can be calculated. So we have enough data points to construct r and evaluate it to find the lost packets. So both the sender and the receiver require O(n (n − k)) operations and only O(n − k) space for operating 'on the fly'.

<div class="mw-heading mw-heading4"><h4 id="Real_world_implementation">Real world implementation</h4></div>

This process is implemented by <a href="Reed%E2%80%93Solomon_code" class="mw-redirect" title="Reed–Solomon code">Reed–Solomon codes</a>, with code words constructed over a <a href="Finite_field" title="Finite field">finite field</a> using a <a href="Vandermonde_matrix" title="Vandermonde matrix">Vandermonde matrix</a>.

Most practical erasure codes are <a href="Systematic_code" title="Systematic code">systematic codes</a> -- each one of the original k symbols can be found copied, unencoded, as one of the n message symbols.<a href="#cite_note-vinayak-12">[12]</a>

(Erasure codes that support <a href="Secret_sharing" title="Secret sharing">secret sharing</a> never use a systematic code).

<div class="mw-heading mw-heading2"><h2 id="Near-optimal_erasure_codes">Near-optimal erasure codes</h2></div>

Near-optimal erasure codes require (1 + ε)k symbols to recover the message (where ε>0). Reducing ε can be done at the cost of CPU time.

Near-optimal erasure codes trade correction capabilities for computational complexity: practical algorithms can encode and decode with linear time complexity.

<a href="Fountain_code" title="Fountain code">Fountain codes</a> (also known as rateless erasure codes) are notable examples of near-optimal erasure codes. They can transform a k symbol message into a practically infinite encoded form, i.e., they can generate an arbitrary amount of redundancy symbols that can all be used for error correction. Receivers can start decoding after they have received slightly more than k encoded symbols.

Regenerating codes address the issue of rebuilding (also called repairing) lost encoded fragments from existing encoded fragments. This issue occurs in distributed

storage systems where communication to maintain encoded redundancy is a problem.<a href="#cite_note-vinayak-12">[12]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications_of_erasure_coding_in_storage_systems">Applications of erasure coding in storage systems</h2></div>

Erasure coding is now standard practice for reliable data storage.<a href="#cite_note-13">[13]</a><a href="#cite_note-14">[14]</a><a href="#cite_note-bbeach-15">[15]</a>

In particular, various implementations of Reed-Solomon erasure coding are used by <a href="Apache_Hadoop" title="Apache Hadoop">Apache Hadoop</a>, the <a href="RAID-6" class="mw-redirect" title="RAID-6">RAID-6</a> built into Linux, Microsoft Azure, Facebook cold storage, and Backblaze Vaults.<a href="#cite_note-bbeach-15">[15]</a><a href="#cite_note-vinayak-12">[12]</a>

The classical way to recover from failures in storage systems was to use replication. However, replication incurs significant overhead in terms of wasted bytes. Therefore, increasingly large storage systems, such as those used in data centers use erasure-coded storage. The most common form of erasure coding used in storage systems is <a href="Reed%E2%80%93Solomon_error_correction" title="Reed–Solomon error correction">Reed-Solomon (RS) code</a>, an advanced mathematics formula used to enable regeneration of missing data from pieces of known data, called parity blocks. In a (k, m) RS code, a given set of k data blocks, called "chunks", are encoded into (k + m) chunks. The total set of chunks comprises a stripe. The coding is done such that as long as at least k out of (k + m) chunks are available, one can recover the entire data. This means a (k, m) RS-encoded storage can tolerate up to m failures.

Example: In RS (10, 4) code, which is used in Facebook for their <a href="HDFS" class="mw-redirect" title="HDFS">HDFS</a>,<a href="#cite_note-16">[16]</a> 10 MB of user data is divided into ten 1MB blocks. Then, four additional 1 MB parity blocks are created to provide redundancy. This can tolerate up to 4 concurrent failures. The storage overhead here is 14/10 = 1.4X.

In the case of a fully replicated system, the 10 MB of user data will have to be replicated 4 times to tolerate up to 4 concurrent failures. The storage overhead in that case will be 50/10 = 5 times.

This gives an idea of the lower storage overhead of erasure-coded storage compared to full replication and thus the attraction in today's storage systems.

Initially, erasure codes were used to reduce the cost of storing "cold" (rarely-accessed) data efficiently; but erasure codes can also be used to improve performance serving "hot" (more-frequently-accessed) data.<a href="#cite_note-vinayak-12">[12]</a>

<a href="RAID" title="RAID">RAID</a> N+M divides data blocks across N+M drives, and can recover all the data when any M drives fail.<a href="#cite_note-xinnor-1">[1]</a>

In particular, RAID 7.3 refers to triple-parity RAID, and can recover all the data when any 3 drives fail.<a href="#cite_note-17">[17]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Here are some examples of implementations of the various codes:

<div class="mw-heading mw-heading3"><h3 id="Near_optimal_erasure_codes">Near optimal erasure codes</h3></div>

<ul><li><a href="Tornado_codes" class="mw-redirect" title="Tornado codes">Tornado codes</a></li>

<li><a href="Low-density_parity-check_codes" class="mw-redirect" title="Low-density parity-check codes">Low-density parity-check codes</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Near_optimal_fountain_(rateless_erasure)_codes">Near optimal fountain (rateless erasure) codes</h3></div>

<ul><li><a href="Fountain_code" title="Fountain code">Fountain code</a></li>

<li><a href="Online_codes" title="Online codes">Online codes</a></li>

<li><a href="LT_codes" class="mw-redirect" title="LT codes">LT codes</a></li>

<li><a href="Raptor_codes" class="mw-redirect" title="Raptor codes">Raptor codes</a></li>

<li><a href="Linear_network_coding" title="Linear network coding">Network Codes</a></li>

<li><a href="Triangular_network_coding" title="Triangular network coding">Triangular codes</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Optimal_erasure_codes_2">Optimal erasure codes</h3></div>

<ul><li><a href="Parity_(telecommunication)" class="mw-redirect" title="Parity (telecommunication)">Parity</a>: used in <a href="RAID" title="RAID">RAID</a> storage systems.</li>

<li><a href="Parchive" title="Parchive">Parchive</a></li>

<li><a href="Tahoe-LAFS" title="Tahoe-LAFS">Tahoe-LAFS</a> includes <a rel="nofollow" class="external text" href="https://pypi.python.org/pypi/zfec">zfec</a></li>

<li><a href="Reed%E2%80%93Solomon" class="mw-redirect" title="Reed–Solomon">Reed–Solomon codes</a></li>

<li><a rel="nofollow" class="external text" href="http://switzernet.com/people/emin-gabrielyan/051103-erasure-9-5-resilient/">Erasure Resilient Systematic Code</a>, an MDS code outperforming Reed–Solomon in the maximal number of redundant packets, see <a rel="nofollow" class="external text" href="http://switzernet.com/people/emin-gabrielyan/051025-erasure-resilient/">RS(4,2) with 2 bits</a> or <a rel="nofollow" class="external text" href="http://switzernet.com/people/emin-gabrielyan/051027-erasure-9-2-resilient/">RS(9,2) with 3 bits</a></li>

<li>Regenerating Codes<a href="#cite_note-regcodes-18">[18]</a><a href="#cite_note-19">[19]</a></li>

<li>any other <a href="Maximum_distance_separable_code" class="mw-redirect" title="Maximum distance separable code">maximum distance separable code</a></li></ul>

<ul><li><a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">Forward error correction</a> codes.</li>

<li><a href="Secret_sharing" title="Secret sharing">Secret sharing</a> (differs in that the original secret is encrypted and obscured until the decode quorum is reached)</li>

<li><a href="Spelling_alphabet" title="Spelling alphabet">Spelling alphabet</a></li>

<li><a href="Binary_erasure_channel" title="Binary erasure channel">Binary erasure channel</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://xinnor.io/blog/a-guide-to-raid-pt-4-raid-vs-erasure-coding-whats-the-difference/">"RAID vs. Erasure Coding. What's the Difference? | Blog | Xinnor"</a>. The Fastest and Most Reliable Software RAID | Xinnor. 2023-09-03. Retrieved 2024-09-18.</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://ceph.io/en/news/blog/2014/erasure-coding-in-ceph-2/">"Ceph.io — Erasure Coding in Ceph"</a>. ceph.io. 2014-04-07. Retrieved 2024-09-18.</cite>

</li>

<cite id="CITEREFLee2023" class="citation web cs1">Lee, Brandon (2023-12-26). <a rel="nofollow" class="external text" href="https://www.bdrsuite.com/blog/raid-vs-erasure-coding-vs-replication/">"RAID vs Erasure Coding vs Replication"</a>. BDRSuite. Retrieved 2024-09-18.</cite>

</li>

<cite id="CITEREFO'Reilly" class="citation web cs1">O'Reilly, Jim. <a rel="nofollow" class="external text" href="https://www.networkcomputing.com/data-center-networking/raid-vs-erasure-coding">"RAID Vs. Erasure Coding"</a>. www.networkcomputing.com. Retrieved 2024-09-18.</cite>

</li>

Dimitri Pertin, Alexandre van Kempen, Benoît Parrein, Nicolas Normand. <a rel="nofollow" class="external text" href="https://hal.science/hal-01162047/document">"Comparison of RAID-6 Erasure Codes"</a>.

The third Sino-French Workshop on Information and Communication Technologies,

SIFWICT 2015, Jun 2015, Nantes, France. ffhal-01162047f

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.ibm.com/docs/en/storage-scale-ece/5.1.3?topic=issece-understanding-spectrum-scale-erasure-code-edition-fault-tolerance">"Understanding IBM Spectrum Scale Erasure Code Edition fault tolerance"</a>. www.ibm.com. Retrieved 2024-09-18.</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://blog.min.io/erasure-coding-vs-raid/">"Object Storage Erasure Coding vs. Block Storage RAID"</a>. MinIO Blog. 2021-07-27. Retrieved 2024-09-18.</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.computerweekly.com/feature/Erasure-coding-versus-RAID-as-a-data-protection-method">"Erasure coding vs Raid as a data protection method | Computer Weekly"</a>. ComputerWeekly.com. Retrieved 2024-09-18.</cite>

</li>

<cite id="CITEREFKruth2023" class="citation web cs1">Kruth, Peter (2023-10-04). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20231004193238/https://blog.huawei.com/2021/11/30/erasure-code-raid-as-it-should-be/">"Erasure Code: RAID As It Should Be – Huawei BLOG"</a>. Archived from <a rel="nofollow" class="external text" href="https://blog.huawei.com/2021/11/30/erasure-code-raid-as-it-should-be/">the original</a> on 2023-10-04. Retrieved 2024-09-18.</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://blog.min.io/erasure-coding/">"Erasure Coding 101"</a>. MinIO Blog. 2022-04-25. Retrieved 2024-09-18.</cite>

</li>

<cite id="CITEREFBhaskaran2018" class="citation web cs1">Bhaskaran, Dinesh Kumar (July 6, 2018). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200807015110/https://www.datacenterdynamics.com/en/opinions/why-erasure-coding-is-the-future-of-data-resiliency/">"Why erasure coding is the future of data resiliency"</a>. Archived from <a rel="nofollow" class="external text" href="https://www.datacenterdynamics.com/en/opinions/why-erasure-coding-is-the-future-of-data-resiliency/">the original</a> on August 7, 2020.</cite>

</li>

Rashmi Vinayak.

<a rel="nofollow" class="external text" href="https://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-155.html">"Erasure Coding for Big-data Systems: Theory and Practice"</a>.

2016.

p. 2: section "Abstract".

p. 9: section "Systematic codes".

p. 12: section "Regenerating codes".

</li>

<a rel="nofollow" class="external text" href="https://www.usenix.org/conference/fast16/training-program/session/erasure-encoding%E2%80%94practice-and-principles">"Erasure Encoding—Practice and Principles"</a>.

2016.

</li>

Matt Sarrel.

<a rel="nofollow" class="external text" href="https://blog.min.io/erasure-coding/">"Erasure Coding 101"</a>.

2022.

</li>

Brian Beach.

<a rel="nofollow" class="external text" href="https://www.backblaze.com/blog/reed-solomon/">"Backblaze Open-sources Reed-Solomon Erasure Coding Source Code"</a>.

2015.

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFXiaSaxenaBlaumPease2015" class="citation book cs1">Xia, Mingyuan; Saxena, Mohit; Blaum, Mario; Pease, David A. (2015). <a rel="nofollow" class="external text" href="https://www.usenix.org/conference/fast15/technical-sessions/presentation/xia">A Tale of Two Erasure Codes in {HDFS}</a>. pp. 213–226. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-931971-20-1</bdi>.</cite>

</li>

Adam Leventhal.

<a rel="nofollow" class="external text" href="https://dl.acm.org/doi/pdf/10.1145/1661785.1670144">""Triple-parity RAID and beyond"</a>.

2009.

</li>

<li id="cite_note-regcodes-18"><a href="#cite_ref-regcodes_18-0">^</a> <cite id="CITEREFDimakisGodfreyWuWainwright2010" class="citation journal cs1">Dimakis, Alexandros G.; Godfrey, P. Brighten; Wu, Yunnan; Wainwright, Martin J.; Ramchandran, Kannan (September 2010). "Network Coding for Distributed Storage Systems". IEEE Transactions on Information Theory. 56 (9): 4539–4551. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0702015">cs/0702015</a>. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.6892">10.1.1.117.6892</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2010.2054295">10.1109/TIT.2010.2054295</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:260559901">260559901</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170731144507/http://storagewiki.ece.utexas.edu/doku.php">"home [Erasure Coding for Distributed Storage Wiki]"</a>. 2017-07-31. Archived from <a rel="nofollow" class="external text" href="http://storagewiki.ece.utexas.edu/doku.php">the original</a> on 2017-07-31. Retrieved 2023-08-20.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://jerasure.org/">Jerasure</a> is a Free Software library implementing Reed-Solomon and Cauchy erasure code techniques with SIMD optimisations.</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160303184031/http://info.iet.unipi.it/~luigi/fec.html">Software FEC in computer communications</a> by Luigi Rizzo describes optimal erasure correction codes</li>

<li><a rel="nofollow" class="external text" href="http://feclib.sourceforge.net">Feclib</a> is a near optimal extension to Luigi Rizzo's work that uses band matrices. Many parameters can be set, like the size of the width of the band and size of the finite field. It also successfully exploits the large <a href="Processor_register" title="Processor register">register</a> size of modern CPUs. How it compares to the near optimal codes mentioned above is unknown.</li>

<li><a rel="nofollow" class="external text" href="https://archive.today/20140620164304/http://storagewiki.ece.utexas.edu/?id=wiki:definitions:repair_problem">Coding for Distributed Storage wiki</a> for regenerating codes and rebuilding erasure codes.</li>

<li><a rel="nofollow" class="external text" href="http://ecip.org/">ECIP "Erasure Code Internet Protocol"</a> Developed in 1996, was the first use of FEC "Forward Error correction" on the Internet. It was first used commercially to *<a rel="nofollow" class="external text" href="http://www.dnull.com/~sokol/clarke.html">stream live video of Sir Arthur C. Clarke in Sri Lanka to UIUC in Indiana</a>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-30" href="https://en.wikipedia.org/wiki/?title=Erasure_code&oldid=1298047069">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>